package org.algorithm.熊猫.数组.三月.第四周;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhx
 * @date 2022-03-21 星期一18:26
 *
 * url: https://leetcode-cn.com/problems/pascals-triangle-ii/
 */
public class 杨辉三角II {

    public static void main(String[] args) {
        System.out.println(getRow(3));
    }


    /**
     * 输入: rowIndex = 3
     * 输出: [1,3,3,1]
     *
     * 输入: rowIndex = 0
     * 输出: [1]
     *
     *
     * 输入: rowIndex = 1
     * 输出: [1,1]
     */
    public static List<Integer> getRow(int numRows) {
        if (numRows == 0) {
            return (Arrays.asList(1));
        }
        if (numRows == 1) {
            return  Arrays.asList(1, 1);
        }

        List<List<Integer>> result = new ArrayList<>();
        ArrayList<Integer> e = new ArrayList<>();
        e.add(1);
        result.add(e);
        e = new ArrayList<>();
        e.add(1);
        e.add(1);
        result.add(e);
        for (int i = 2; i <= numRows; i++) {
            List<Integer> temp = new ArrayList<>();
            //开头加进去
            temp.add(1);
            int count = i-1;
            //中间数字值为，上一个数组的头节点和下一个节点之和
            List<Integer> lastList = result.get(result.size() - 1);
            int lastStart = 0;
            while (count > 0) {
                temp.add(lastList.get(lastStart) + lastList.get(lastStart + 1));
                lastStart++;
                count--;
            }
            //结尾加进去
            temp.add(1);
            result.add(temp);
        }

        return result.get(result.size()-1);
    }
}
